# -*- coding: utf-8 -*-

"""
    Time    : 2020/11/24 11:11 下午
    Author  : Thinkgamer
    File    : 01-单链表.py
    Desc    : 单链表相关知识复习
    知识要点：
        1、链表返回的是头节点  「重要」
        2、数组转链表
        3、链表逆序输出 / 链表逆序输出（不额外申请空间）
        4、链表指定位置逆序（eg：长度为5的链表，虚拟2-4）
        5、删除链表节点
        6、增加链表节点
        7、修改链表结点
        8、搜索指定值是否在链表中
"""


# 定义链表结构
class ListNode:
	def __init__(self, val=0, next=None):
		self.val = val
		self.next = next

class ListAction:
	def __init__(self):
		pass

	# 输出链表
	def printList(self, _list):
		while _list:
			print(_list.val, end=" ")
			_list = _list.next
		print("\n--------------- end!")

	# 数组转链表
	def array_to_list(self, arr):
		# 将数组的头元素赋给链表的首位
		_list = ListNode(arr[0])
		other = _list
		# 遍历剩下的值
		for one in arr[1:]:
			# 创建当前元素的list
			temp = ListNode(one)
			other.next = temp
			other = temp

		self.printList(_list)
		return _list

	# 链表逆序输出
	def inverse_list(self, _list):
		# 基于传入链表的头部元素创建新的链表
		new_list = ListNode(_list.val)
		# next 为遍历的终止条件，头部元素已经使用过，因此指向下一个
		next = _list.next
		while next:
			# 创建临时链表
			temp = ListNode(next.val)
			# 将临时链表的指针指向 创建的新链表
			temp.next = new_list
			# 再将临时链表赋值给临时链表
			new_list = temp
			# 指向下一个
			next = next.next
		self.printList(new_list)
		return new_list

	# 链表逆序输出(会改变原来的 _list)  1 2 3 4 5
	def inverse_list_v2(self, _list):
		# 创建一个空的链表
		new_list = ListNode(_list.val)
		_list = _list.next
		while _list:
			next = _list.next
			_list.next = new_list
			new_list = _list
			_list = next
		self.printList(new_list)
		return new_list

	def inverse_list_loc(self, _list, start, end):
		# [2, 1, 4, 3, 6, 5] / 3,5
		# 这里先不考虑 start=1, end = len(_list), 后续刷到这道题的时候再优化
		i = 1
		# 存储最终结果的链表
		new_list = ListNode()
		# 临时的链表，可以理解为指针
		other = new_list
		
		# start 前的一个节点
		prehead = ListNode()
		# start 对应的节点
		head = ListNode()
		
		# start 之前的链表 不需要进行逆序
		while i <= start - 1 and _list:
			temp = ListNode(_list.val)
			# prehead的值每次都进行更新
			prehead = temp
			
			other.next = temp
			other = temp
			_list = _list.next
			i += 1
		
		# 主要是为了校验目前输出的 new_list是否满足期望， prehead是否满足期望
		self.printList(new_list.next)
		print("prehead: {}".format(prehead.val))
		
		# 记录 head值，并进行打印和校验
		head.val = _list.val
		print("head: {}".format(head.val))

		other = head
		_list = _list.next
		i += 1
		# start 到 end之间，进行逆序
		while i <= end and _list:
			next = _list.next
			_list.next = other
			other = _list
			_list = next
			i += 1
			
		self.printList(other)
		
		prehead.next = other
		head.next = _list
		self.printList(new_list.next)
	
	# 删除链表中的第 target 个节点，如果该值在链表中进行删除，不在的话返回原链表
	def delete_node(self, _list, loc):
		i = 1
		if loc == 1:  # 如果删除的是第一个元素
			_list = _list.next
		else:  # 如果删除的不是第一个元素
			next = _list
			while next:
				if i == loc - 1:
					next.next = next.next.next
				else:
					next = next.next
				i += 1
		self.printList(_list)
		return _list

	# 在指定位置为链表增加新的节点，原先位置的节点后移
	def add_node(self, _list, target, loc):
		if loc == 1:  # 表示在第一个位置插入新的节点
			temp = ListNode(target)
			temp.next = _list
			_list = temp
		else:  # 表示在其他位置插入新的节点
			i = 1
			next = _list
			while next:
				if i == loc - 1:
					temp = ListNode(target)
					old_next = next.next
					next.next = temp
					temp.next = old_next
				else:
					next = next.next
				i += 1
		self.printList(_list)
		return _list

	# 修改指定位置的节点值
	def change_list(self, _list, target, loc):
		if loc == 1:
			_list.val = target
		else:
			i = 1
			next = _list
			while next:
				if i == loc - 1:
					temp = ListNode(target)
					temp.next = next.next.next
					next.next = temp
				else:
					next = next.next
				i += 1
		self.printList(_list)
		return _list

	# 搜索给定值是否在链表中，是的话返回1，否的话返回0
	def search_list(self, _list, target):
		next = _list
		result = 0
		while next:
			if next.val == target:
				result = 1
			next = next.next
		print("指定值是否在链表中：{}".format(result))
		return result


if __name__ == "__main__":
	action = ListAction()
	# 数组转链表
	_list = action.array_to_list([2, 1, 4, 3, 6, 5])
	# 链表逆序输出
	# action.inverse_list(_list)
	# action.inverse_list_v2(_list)
	# 链表指定位置逆序
	action.printList(_list)
	action.inverse_list_loc(_list, 3, 5)
	# 删除链表中的第 target 个节点
	# action.printList(_list)
	# action.delete_node(_list, loc=3)
	# 在位置 loc 插入新的节点值 target
	# action.printList(_list)
	# action.add_node(_list, target=7, loc=3)
	# 修改指定位置的节点值
	# action.printList(_list)
	# action.change_list(_list, target=8, loc=3)
	# 搜索指定值是否在链表中
	# action.search_list(_list, 7)
